package com.heima.leetcode.practice;

/**
 * leetcode 583. 两个字符串的删除操作
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/11 20:53
 */
public class E583 {

    /**
     * <h3>方法一：采用的二维的动态规划</h3>
     * 删除两个字符串 word1 和 word2 的最小删除数
     * @param word1 word1
     * @param word2 word2
     * @return 最小删除数
     */
    public int minDistance1(String word1, String word2) {
        return word1.length() + word2.length() - (longestCommonSubsequence1(word1, word2) << 1);
    }

    /**
     * <h3>方法二；采用的一维的动态规划</h3>
     * 删除两个字符串 word1 和 word2 的最小删除数
     * @param word1 word1
     * @param word2 word2
     * @return 最小删除数
     */
    public int minDistance2(String word1, String word2) {
        return word1.length() + word2.length() - (longestCommonSubsequence2(word1, word2) << 1);
    }

    /*
              a   b   c   d  str2
          0   0   0   0   0
      a   0   1   1   1   1
      c   0   1   1   2   2
      e   0   1   1   2   2
     str1

      dp[i][j]表示str1前0 - i-1个字符形成的字符串和str2前0 - j-1个字符形成的字符串的最长公共子序列的长度
      其中只有当i>0&&j>0的时候才是有效部分

      if (str1[i] == str2[j]) {
          dp[i][j] = dp[i - 1][j - 1] + 1;
      }else{
          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
     */

    /**
     * 最长公共子序列长度
     * @param str1 字符串1
     * @param str2 字符串2
     * @return 最长公共子序列的长度
     */
    private int longestCommonSubsequence1(String str1, String str2) {
        char[] str1Array = str1.toCharArray();
        char[] str2Array = str2.toCharArray();
        // 1. 创建二维数组
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        // 2. 填充i>0 && j>0部分的动态数组
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < str2.length() + 1; j++) {
                if (str1Array[i - 1] == str2Array[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        // 3. 返回最长公共子序列的长度
        return dp[str1.length()][str2.length()];
    }

    /*
              a   b   c   d  str2
          0   0   0   0   0
      a   0   1   1   1   1
      c   0   1   1   2   2
      e   0   1   1   2   2
     str1

      dp[i][j]表示str1前0 - i-1个字符形成的字符串和str2前0 - j-1个字符形成的字符串的最长公共子序列的长度
      其中只有当i>0&&j>0的时候才是有效部分

      if (str1[i] == str2[j]) {
          dp[i][j] = dp[i - 1][j - 1] + 1;
      }else{
          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
     */

    /**
     * 最长公共子序列长度，用一维数组优化
     * @param str1 字符串1
     * @param str2 字符串2
     * @return 最长公共子序列的长度
     */
    private int longestCommonSubsequence2(String str1, String str2) {
        char[] str1Array = str1.toCharArray();
        char[] str2Array = str2.toCharArray();
        // 1. 创建一维数组
        int[] dp = new int[str2.length() + 1];
        // 2. 填充i>0 && j>0部分的动态数组
        for (int i = 1; i < str1Array.length + 1; i++) {
            int lastRowPrev = 0; // 用于记录dp[j]对应的上一行左边一个节点的值，j从1开始，prev初始就设置为0，而且每一行开始的时候都要设置为0
            for (int j = 1; j < str2Array.length + 1; j++) {
                int temp = dp[j]; // 用于记录上一行的dp[j]的值，当j指针移动到j+1时，此时的temp就是j指针的上一行的prev值
                if (str1Array[i - 1] == str2Array[j - 1]){
                    dp[j] = lastRowPrev + 1; // 用的是上一行的prev值
                }else {
                    dp[j] = Math.max(dp[j], dp[j - 1]); // dp[j - 1]用的是当前行的prev值
                }
                lastRowPrev = temp; // 更新prev
            }
        }
        // 3. 返回最长公共子序列的长度
        return dp[str2Array.length];
    }
}
